Home > Search Results: keywords:"kreslení grafů|geometrický graf|nekřížící se alternující cesta|doubarevná množina bodů|nejdelší společná podposloupnost"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.00 seconds. 
Drawing geometric graphs on red-blue point sets
 Soukup, Jan ; Kynčl, Jan (advisor) ; Kratochvíl, Jan (referee)
Consider a set B of blue points and a set R of red points in the plane such that R ∪ B is in general position. A graph drawn in the plane whose edges are straight-line segments is called a geometric graph. We investigate the problem of drawing non-crossing properly colored geometric graphs on the point set R ∪ B. We show that if ||B| − |R|| ≤ 1 and a subset of R forms the vertices of a convex polygon separating the points of B, lying inside the polygon, from the rest of the points of R, lying outside the polygon, then there exists a non-crossing properly colored geometric path on R∪B covering all points of R ∪ B. If R∪B lies on a circle, the size of the longest non-crossing geometric path is related to the size of the largest separated matching; a separated matching is a non-crossing properly colored geometric matching where all edges can be crossed by a line. A discrepancy of R ∪ B is the maximal difference between cardinalities of color classes of intervals on the circle. When the discrepancy of R ∪ B is at most 2, we show that there is a separated matching covering asymptotically 4 5 of points of R ∪ B. During this proof we use a connection between separated matchings and the longest common subsequences between two binary sequences where the symbols correspond to the colors of the points.
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English